/*
 * ds.cpp
 *
 *  Created on: Sep 14, 2012
 *      Author: xx255000
 */

#include "../includes/ds.h"

LinkListNode* CreateLinkedList(int *a, int from, int to, LinkListNode* l) {
	assert(from >=0 && from < to);
	l = (l == NULL) ? new LinkListNode : l;
	LinkListNode* p = l;
	p->value = a[from];
	for(int i = from + 1; i < to; i++) {
		p->next = new LinkListNode;
		p->next->value = a[i];
		p = p->next;
	}
	p->next = NULL;
	return l;
}

void DestroyLinkedList(LinkListNode* l) {
	LinkListNode* p = l;
	while(l != NULL) {
		l = l->next;
		delete p;
		p = l;
	}
	if(p != NULL)
		delete p;
}

void PrintLinkedList(LinkListNode* l) {
	LinkListNode* p = l;
	while(p != NULL) {
		cout<<p->value<<"\t";
		p = p->next;
	}
	cout<<endl;
}

LinkListNode* ReverseLinkedList(LinkListNode* l) {
	LinkListNode* p = l, *q = NULL, *r = (p == NULL) ? NULL : p->next;
	while(r != NULL) {
		p->next = q;
		q = p;
		p = r;
		r = r->next;
	}
	p->next = q;
	l = p;
	return l;
}

LinkListNode* ReverseLinkedListRecursively(LinkListNode* l) {
	if(l == NULL) {
		return NULL;
	}
	if(l->next == NULL) {
		return l;
	}
	LinkListNode* q = ReverseLinkedListRecursively(l->next);
	l->next->next = l;
	l->next = NULL;
	return q;
}

bool TwoLinkedListCrosses(LinkListNode* h, LinkListNode* l) {
	LinkListNode* p = h, *q = l;
	while(p->next != NULL) {
		p = p->next;
	}
	while(q->next != NULL) {
		q = q->next;
	}

	return p == q;
}

void PrintBackwardsKthNode(LinkListNode* l, int k) {
	LinkListNode* p = l, *q = p;
	for(int i = 1; i < k && p != NULL; i++) {
		p = p->next;
	}
	while(p != NULL && p->next != NULL) {
		p = p->next;
		q = q->next;
	}
	if(q != NULL) {
		cout<<q->value<<endl;
	}
}




TreeNode* CreateTree(int *a, int from, int to, TreeNode* r) {
	assert(from >= 0 && from < to);
	int size = to - from;
	TreeNode** nodes = new TreeNode*[size];
	for(int i = 0; i < size; i++) {
		if(a[i - from] == 0) {
			nodes[i] = NULL;
		} else {
			nodes[i] = new TreeNode;
			nodes[i]->value = a[i - from];
		}
	}
	for(int i = 1; i <= size; i++) {
		if(nodes[i - 1] != NULL) {
			nodes[i - 1]->left = (2 * i <= size) ? nodes[2 * i - 1] : NULL;
			nodes[i - 1]->right = (2 * i + 1 <= size) ? nodes[2 * i] : NULL;
		}
	}
	r = nodes[0];
	return r;
}

void DestroyTree(TreeNode* n) {
	if(n == NULL) {
		return;
	}

	DestroyTree(n->left);
	DestroyTree(n->right);
	delete n;
	n = NULL;
}

void RecursivelyPreVisitTree(TreeNode* n) {
	if(n == NULL)
		return;

	cout<<n->value<<"\t";
	RecursivelyPreVisitTree(n->left);
	RecursivelyPreVisitTree(n->right);
}

void RecursivelyMidVisitTree(TreeNode* n) {
	if(n == NULL)
		return;

	RecursivelyMidVisitTree(n->left);
	cout<<n->value<<"\t";
	RecursivelyMidVisitTree(n->right);
}

void RecursivelyPostVisitTree(TreeNode* n) {
	if(n == NULL)
		return;

	RecursivelyPostVisitTree(n->left);
	RecursivelyPostVisitTree(n->right);
	cout<<n->value<<"\t";
}

TreeNode* RecursivelySwitchTree(TreeNode* n) {
	if(n == NULL) {
		return NULL;
	}
	TreeNode* l = RecursivelySwitchTree(n->left);
	TreeNode* r = RecursivelySwitchTree(n->right);
	n->left = r;
	n->right = l;
	return n;
}

void SwitchTree(TreeNode* n) {
	if(n == NULL) {
		return;
	}
	stack<TreeNode*> s;
	s.push(n);
	while(!s.empty()) {
		TreeNode* root = s.top();
		s.pop();
		TreeNode* temp = root->left;
		root->left = root->right;
		root->right = temp;
		if(root->left != NULL) {
			s.push(root->right);
		}
		if(root->left != NULL) {
			s.push(root->left);
		}
	}
}

void VisitTreeByLevel(TreeNode* n) {
	queue<TreeNode*> q;
	if(n != NULL) {
		q.push(n);
	}
	while(!q.empty()) {
		TreeNode* p = q.front();
		cout<<p->value<<"\t";
		q.pop();
		if(p->left != NULL) {
			q.push(p->left);
		}
		if(p->right != NULL) {
			q.push(p->right);
		}
	}
}

bool ExistPathEqualsN(TreeNode* t, int n, stack<TreeNode*> &s) {
	bool flag = false;
	if(t == NULL) {
		return false;
	}
	if(t->left == NULL && t->right == NULL && t->value == n) {
		s.push(t);
		cout<<endl;
		return true;
	}
	if(ExistPathEqualsN(t->left, n - t->value, s)) {
		s.push(t);
		while(!s.empty()) {
			TreeNode* p = s.top();
			cout<<p->value<<"\t";
			s.pop();
		}
		flag = true;
	}
	if(ExistPathEqualsN(t->right, n - t->value, s)) {
		s.push(t);
		while(!s.empty()) {
			TreeNode* p = s.top();
			cout<<p->value<<"\t";
			s.pop();
		}
		flag = true;
	}
	return flag;
}

void PrintPathEqualsN(TreeNode* t, int n) {
	stack<TreeNode*> s;
	ExistPathEqualsN(t, n, s);
}

TreeNode* GetNearestCommonParent(TreeNode* n, TreeNode* n1, TreeNode* n2) {
	if(n == NULL) {
		return NULL;
	}
	if(n == n1 || n == n2) {
		return n;
	}
	TreeNode* l = GetNearestCommonParent(n->left, n1, n2);
	TreeNode* r = GetNearestCommonParent(n->right, n1, n2);
	if(l == NULL) {
		return r;
	} else if(r == NULL) {
		return l;
	} else {
		return n;
	}
}

int maxSum = 0;

int GetMaxSubTreeSum(TreeNode* n) {
	if(n == NULL) {
		return 0;
	}
	int leftSum = GetMaxSubTreeSum(n->left);
	int rightSum = GetMaxSubTreeSum(n->right);
	maxSum = rightSum > leftSum ? rightSum : leftSum;
	int totalSum = leftSum + rightSum + n->value;
	maxSum = maxSum > totalSum ? maxSum : totalSum;

	return maxSum;
}




DBListNode* dbListLastPtr = NULL;
DBListNode* dbListHead = NULL;

void ConvertToDBList(TreeNode* t, DBListNode* &l) {
	if(t != NULL) {
		ConvertToDBList(t->left, l);
		if(dbListLastPtr != NULL) {
			dbListLastPtr->right = t;
			t->left = dbListLastPtr;
		} else {
			dbListHead = t;
		}
		dbListLastPtr = t;
		ConvertToDBList(t->right, l);
	}
	l = dbListHead;
}

void PrintDBList(DBListNode* l) {
	DBListNode* p = l;
	while(p != NULL) {
		cout<<p->value<<"\t";
		p = p->right;
	}
	cout<<endl;
}

void DeleteDBList(DBListNode* l) {
	DBListNode* p = l, *q;
	while(p != NULL) {
		q = p->right;
		delete p;
		if(q != NULL) {
			q->left = NULL;
		}
		p = q;
	}
}

void PrintStack(stack<int> &s) {
	if(!s.empty()) {
		int top = s.top();
		s.pop();
		cout<<top<<"\t";
		PrintStack(s);
		s.push(top);
	}
}

void PushToBottom(stack<int>& s, int top) {
	if(!s.empty()) {
		int temp = s.top();
		s.pop();
		PushToBottom(s, top);
		s.push(temp);
	} else {
		s.push(top);
	}
}

stack<int> & RecursivelyReverseStack(stack<int> &s) {
	if(!s.empty()) {
		int top = s.top();
		s.pop();
		RecursivelyReverseStack(s);
		PushToBottom(s, top);
	}
	return s;
}
